package leetcode

import kotlinetc.println

//https://leetcode.com/problems/count-numbers-with-unique-digits/
/**
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:

Input: 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100,
excluding 11,22,33,44,55,66,77,88,99
Accepted
64,433
Submissions
136,406
 */
fun main(args: Array<String>) {
    countNumbersWithUniqueDigits(3).println()
}


//Dp
/**
可以用动态规划来做
 */
fun countNumbersWithUniqueDigits(n: Int): Int {

    if (n == 0) return 1

    if (n == 1) return 10

    var res = 10

    var count = 9

    for (i in 2..n) {
        count *= 11 - i
        res += count
    }

    return res
}